题解P1772 [ZJOI2006]物流运输

P1772 [ZJOI2006]物流运输

看完这道题，很容易想到需要用最短路，但是只用最短路显然是不行的，因为运输路线不止一条，

所以如果每一天都选择最短的路线答案可能并不是最优，所以这时候就需要考虑DP，

刚开始我想的是用状态压缩把所有可能的路线算出来，但很快就被我否决了，因为时间复杂度显然超了，所以考虑其他方法

观察样例得出，有可能一段时间内的最短路是一样的，所以考虑定义一个数组$dis_{i,j}$表示第$i$天到第$j$天都可以走的最短的路线,

然后就可以定义状态$f_i$表示前$i$天的最短花费,考虑将n天划分成若干段进行转移即可

得出状态转移方程
$f_i=\min\limits_{0\le j <i}f_j+(i-j) * (dis_{j+1,i})+k$

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N = 2e5 + 5;
typedef pair<int, int> PII;
typedef long long ll;

ll dis[105][105], f[105];
int n, m, k, e, dist[25];
int head[N], ver[N], net[N], edge[N], idx;
priority_queue<PII, vector<PII>, greater<PII> > q;
bool is[25][105], vis[25];

void add(int a, int b, int c)
{
    net[idx] = head[a];
    ver[idx] = b;
    edge[idx] = c;
    head[a] = idx++;
}

int Dij(int x, int y)//最短路
{
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= m; i++)
        for (int j = x; j <= y; j++)
            if (is[i][j])
                vis[i] = true;
    q.push(make_pair(0, 1)), dist[1] = 0;
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; ~i; i = net[i])
        {
            int v = ver[i];
            if (dist[v] > dist[u] + edge[i])
            {
                dist[v] = dist[u] + edge[i];
                q.push({dist[v], v});
            }
        }
    }
    return dist[m];
}

int main()
{
    memset(f, 0x3f, sizeof(f));
    memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &k, &e);
    for (int i = 1; i <= e; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w), add(v, u, w);
    }
    int d;
    scanf("%d", &d);
    for (int i = 1; i <= d; i++)
    {
        int p, a, b;
        scanf("%d%d%d", &p, &a, &b);
        for (int i = a; i <= b; i++)
            is[p][i] = true;
    }
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            dis[i][j] = Dij(i, j);
    f[0] = -k;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            f[i] = min(f[i], f[j] + (i - j) * dis[j + 1][i] + k);  
    printf("%d", f[n]);
}